package com.cjm.algorithm.tree;


import com.cjm.algorithm.TreeNode;

public class BuildTree {
    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        if (postorder.length == 0) {
            return null;
        }
        return doBuild(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    public static TreeNode doBuild1(int[] preOrder, int[] postOrder, int preHeader, int preTail, int postHeader, int postTail) {
        if (postHeader > postTail) {
            return null;
        }
        int rootValue = postOrder[postTail];
        TreeNode treeNode = new TreeNode();
        treeNode.val = rootValue;

        int mid = 0;
        while (preOrder[mid] != rootValue) {
            mid ++;
        }
        treeNode.left = doBuild1(preOrder, postOrder, preHeader, preHeader + mid - 1,
                postHeader, postHeader + mid - 1);
        treeNode.right = doBuild1(preOrder, postOrder, preHeader + mid + 1, preTail,
                postHeader + mid, preTail - 1);
        return treeNode;
    }

    public static TreeNode doBuild(int[] preOder, int preHeader, int preTail, int[] postOrder, int postHeader,
           int postTail) {
        if (postHeader > postTail) {
            return null;
        }
        int rootValue = postOrder[postTail];
        TreeNode root = new TreeNode();
        root.val = rootValue;

        if (postHeader == postTail) {
            return root;
        }
        int mid = 0;// 这个是错误的方式, 因为前序遍历与后序遍历的头是不一样的
        while (preOder[preHeader + mid] != rootValue) {
            mid ++;
        }

        root.left = doBuild(preOder, preHeader, preHeader + mid - 1,
                            postOrder, postHeader, postHeader + mid - 1);

        root.right = doBuild(preOder, preHeader + mid + 1, preTail,
                postOrder, postHeader + mid, postTail - 1);
        return root;
    }
}
